/*
 * @lc app=leetcode.cn id=765 lang=javascript
 *
 * [765] 情侣牵手
 */

// @lc code=start
/**
 * @param {number[]} row
 * @return {number}
 */

/**
 * 思路： 
 * 遍历row数组，每次取出两个人，
 * 我们发现情侣的编号是从0开始的，编号一个是奇数一个是偶数，并且此奇数=此偶数+1。
 * 所以我们就可以认定如果两个人的编号除以2后相等，就证明两个人是情侣，不需要进行调整。
 * 否则，就需要将两个编号除以2后的结果进行连通，然后进行交换调整。
 * 当N-1对情侣交换配对成功的时候，最后 一对情侣也会配对成功。
 * 我们只需要记录连通合并的次数就可以得到调整的次数。 
 *  */

class UnionSet {
  constructor (n = 100) {
    this.father = new Array(n);
    this.count = n;
    this.init(n);
  }
  init(n) {
    for (let i = 0; i < n; i++) this.father[i] = i;
  }

  // 带路径压缩
  find(x) {
    return this.father[x] = (this.father[x] == x ? x : this.find(this.father[x]));
  }
  // 将 a 合并到 b
  merge(a, b) {
    const fa = this.find(a);
    const fb = this.find(b);
    if (fa === fb) return;
    this.father[fa] = fb;
    this.count--; // 每进行一次合并，集合数减少一个。
  }
}
var minSwapsCouples = function (row) {
  let n = row.length;
  let N = n >> 1; // 最多有N个集合
  const u = new UnionSet(N);
  for (let i = 0; i < n; i += 2) {
    // 编号/2 为应该在的组号
    u.merge(row[i] >> 1, row[i + 1] >> 1);
  }
  return N - u.count;
};
// @lc code=end

